home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d13 / pds300.arc / PDSORT.C < prev    next >
C/C++ Source or Header  |  1991-02-09  |  13KB  |  461 lines
  1. /*
  2.    ****************************  NOTICE!  **************************
  3.    *   Contrary to the current trend  in  MS-DOS  software  this   *
  4.    *   program,  for  whatever  it is worth,  is NOT copyrighted   *
  5.    *   (with the exception of the runtime library  from  Borland   *
  6.    *   International's  Turbo  C)!  The program,  in whole or in   *
  7.    *   part,  may be used freely in any fashion  or  environment   *
  8.    *   desired.  If  you  find this program to be useful to you,   *
  9.    *   do NOT send any contribution to the author;  in the words   *
  10.    *   of  Rick  Conn,   'Enjoy!'  However,   if  you  make  any   *
  11.    *   improvements,  I would enjoy  receiving  a  copy  of  the   *
  12.    *   modified  source.  I  can  be reached,  usually within 24   *
  13.    *   hours,  by  messages  on  any  of  the  Phoenix  systems,   *
  14.    *   particularly:                                               *
  15.    *                                                               *
  16.    *               Technoids Anonymous     [PCBOARD]               *
  17.    *                   (602) 899-4876   300/1200/2400 bps          *
  18.    *                                                               *
  19.    *   All can be reached through PC Pursuit.                      *
  20.    *                                                               *
  21.    *   or:                                                         *
  22.    *                on GEnie, mail address: DON-WILL               *
  23.    *                on CompuServ:           75410,543              *
  24.    *                                                               *
  25.    *   Every  effort has been made to avoid error and moderately   *
  26.    *   extensive testing has been  performed  on  this  program,   *
  27.    *   however, the author does not warrant it to be fit for any   *
  28.    *   purpose  or  to  be  free  from  error  and disclaims any   *
  29.    *   liability for actual or any other damage arising from the   *
  30.    *   use of this program.                                        *
  31.    *****************************************************************
  32. */
  33.  
  34. #include <stdlib.h>
  35. #include <stdio.h>
  36. #include <string.h>
  37. #include <alloc.h>
  38. #include <ctype.h>
  39. #include <dir.h>
  40. #include <dos.h>
  41. #include <limits.h>
  42.  
  43. #include "queue.h"
  44.  
  45. void            GetArgs(int argc, char *argv[]);
  46. void            InvalArgu(char *Msg);
  47. unsigned        FillSortArray(void);
  48. void            Usage(void);
  49. int             isdevice(int handle);
  50.  
  51. void            Merge(void);
  52.  
  53. unsigned long   MaxMem;
  54. unsigned        S_ArraySize;
  55. char          **SortArray;
  56. int             KeyCount = 0;
  57. int             RecLen = -1;
  58. unsigned long   DiskAdr = 0;
  59. unsigned long   NextAdr = 0;
  60. unsigned long   EndAdr;
  61. long            TotalRecs = 0;
  62. long            OutCount = 0;
  63. char            Buffer[512];
  64. FILE           *fin = NULL;
  65. FILE           *fint, *fout;
  66. unsigned long   lnno = 0;
  67. QUE_DEF        *Keys, Runs;
  68. long            BufSize;
  69. char            IntPath[65] = "";
  70.  
  71. unsigned        DeBug = 0;
  72.  
  73. struct KeyEntry {
  74.     int             Begin;
  75.     int             Len;
  76.     char            Order;
  77.     char            Case;
  78.     char            Type;
  79.     };
  80.  
  81. typedef struct RunStruct {
  82.     unsigned long   Begin;
  83.     unsigned long   Count;
  84.     }               RUN_ENT;
  85.  
  86. char            InputName[65] = "";
  87. char            OutName[65] = "";
  88. char            IntName[65] = "";
  89. long            Temp;
  90. int             QuietSwt = 0;
  91. int                Verbose  = 0;
  92.  
  93.  void
  94. main (int argc, char *argv[]) {
  95.     extern int      comp();
  96.  
  97.     unsigned        i;
  98.     unsigned        Count;
  99.     RUN_ENT        *r;
  100.     struct dfree    DiskTab;
  101.     char           *p;
  102.     char            OutDisk;
  103.     char            IntDisk;
  104.     long            DiskFree;
  105.     struct KeyEntry *t;
  106.  
  107.     if ((Keys = malloc(sizeof(QUE_DEF))) == NULL) {
  108.         fprintf(stderr, "Insufficient memory for Key queue.\n");
  109.         exit(12);
  110.         }
  111.     InitQueue(Keys);
  112.     InitQueue(&Runs);
  113.     if (argc < 2) {
  114.         fin = stdin;
  115.         fout = stdout;
  116.         }
  117.     else {
  118.         GetArgs(argc, argv);
  119.         }
  120.     if (RecLen == -1) RecLen = 258;
  121.     if (!QuietSwt)
  122.         fprintf(stderr, "PDSORT Version 3.0.0:  February 5, 1991\n");
  123.     if (fin != stdin) {
  124.         if ((fin = fopen(InputName, "r")) == NULL) {
  125.             fprintf(stderr, "I can't find input file: %s", InputName);
  126.             perror("");
  127.             exit(2);
  128.             }
  129.         }
  130.     if (!isdevice(fileno(fin))) {
  131.         fseek(fin, 0, SEEK_END);
  132.         EndAdr = ftell(fin);
  133.         fseek(fin, 0, SEEK_SET);
  134.         }
  135.     else EndAdr = 0;
  136.  
  137.     if (fin != stdin) {
  138.         if ((p = strchr(OutName, ':')) != NULL) OutDisk = toupper(OutName[0]);
  139.         else OutDisk = getdisk() + 1;
  140.         getdfree(OutDisk, &DiskTab);
  141.         DiskFree = (long) DiskTab.df_avail * DiskTab.df_sclus * DiskTab.df_bsec;
  142.         if (DiskFree < EndAdr) {
  143.             fprintf(stderr, "Insufficient space on output disk.\n");
  144.             exit(5);
  145.             }
  146.         if (IntPath[0] != '\0') {
  147.             if (IntPath[1] == ':') IntDisk = toupper(IntPath[0]);
  148.             else IntDisk = getdisk() + 1;
  149.             }
  150.         else {
  151.             if ((p = strrchr(OutName, '\\')) != NULL)
  152.                 strncpy(IntPath, OutName, (int) (p - OutName + 1));
  153.             else {
  154.                 IntPath[0] = OutDisk + '@';
  155.                 IntPath[1] = ':';
  156.                 IntPath[2] = '\\';
  157.                 getcurdir(OutDisk, &IntPath[3]);
  158.                 }
  159.             if (strchr(IntPath, ':') == NULL) IntDisk = OutDisk;
  160.             else IntDisk = IntPath[0] - '@';
  161.             }
  162.         getdfree(IntDisk, &DiskTab);
  163.         DiskFree = (long) DiskTab.df_avail * DiskTab.df_sclus * DiskTab.df_bsec;
  164.         if (DiskFree < EndAdr) {
  165.             fprintf(stderr, "Insufficient space on intermediate disk.\n");
  166.             exit(6);
  167.             }
  168.         }
  169.     if (Keys->Count == 0) {
  170.         if ((t = malloc(sizeof(struct KeyEntry))) == NULL) {
  171.             fprintf(stderr, "Insufficient memory for Key entry.\n");
  172.             exit(12);
  173.             }
  174.         t->Order = 'a';
  175.         t->Case = 'm';
  176.         t->Type = 'c';
  177.         t->Begin = 0;
  178.         t->Len = RecLen;
  179.         Enque(Keys, t);
  180.         }
  181.     MaxMem = coreleft();
  182.     MaxMem -= 4 * 1024L;
  183.  
  184.     S_ArraySize = (unsigned) (MaxMem / (RecLen + 2 + sizeof(char far *) + 10));
  185.     if (S_ArraySize > UINT_MAX / sizeof(char far *))
  186.         S_ArraySize = UINT_MAX / sizeof(char far *);
  187.     if ((SortArray = malloc(S_ArraySize * sizeof(char far *))) == NULL) {
  188.         fprintf(stderr, "Major Error! Insufficient memory for Sort Array.\n");
  189.         exit(12);
  190.         }
  191.  
  192.     for (i = 0;
  193.          (i < S_ArraySize && coreleft() >= ((4 * 1024L) + RecLen + 2));
  194.          i++) {
  195.         if ((SortArray[i] = malloc(RecLen + 2)) == NULL) {
  196.             fprintf(stderr, "Major Error! Insufficient memory for sort item.\n");
  197.             exit(12);
  198.             }
  199.         }
  200.     S_ArraySize = i;
  201.     if (!QuietSwt)
  202.         fprintf(stderr, "Max records per run = %d\n", S_ArraySize);
  203.  
  204.     BufSize = (coreleft() - 1024) / 2;
  205.  
  206.     if (Verbose && !QuietSwt) printf(" Run # %d\n", Runs.Count + 1);
  207.     Count = FillSortArray();
  208.  
  209.     TotalRecs += Count;
  210.     if (NextAdr >= EndAdr) {
  211.         if (!QuietSwt)
  212.             fprintf(stderr, "Total records read = %ld\n", TotalRecs);
  213.         if (fin != stdin) {
  214.             fclose(fin);
  215.             if ((fout = fopen(OutName, "w")) == NULL) {
  216.                 fprintf(stderr, "I can't create output file: %s", OutName);
  217.                 perror("");
  218.                 exit(7);
  219.                 }
  220.             }
  221.         errno = 0;
  222.         if (Verbose && !QuietSwt) printf("\tSorting\n");
  223.         qsort(SortArray, Count, sizeof(char far *), comp);
  224.  
  225.         if (Verbose && !QuietSwt) printf("\tWriting\n");
  226.         for (i = 0; i < Count; i++) {
  227.             fputs(SortArray[i], fout);
  228.             if (errno) {
  229.                 perror("I/O error on output file");
  230.                 exit(8);
  231.                 }
  232.             OutCount++;
  233.             }
  234.         }
  235.     else {
  236.         while (Count > 0) {
  237.             if (fint == NULL) {
  238.                 strcpy(IntName, IntPath);
  239.                 strcat(IntName, "\\SORT.$$$");
  240.                 if ((fint = fopen(IntName, "w")) == NULL) {
  241.                     fprintf(stderr, "I can't create sort intermediate file: %s", IntName);
  242.                     perror("");
  243.                     exit(9);
  244.                     }
  245.                 errno = 0;
  246.                 }
  247.             DiskAdr = ftell(fint);
  248.  
  249.             if (Verbose && !QuietSwt) printf("\tSorting\n");
  250.             qsort(SortArray, Count, sizeof(char far *), comp);
  251.  
  252.             if ((r = malloc(sizeof(RUN_ENT))) == NULL) {
  253.                 fprintf(stderr, "Insufficient memory for Run Entry!\n");
  254.                 exit(12);
  255.                 }
  256.             r->Begin = DiskAdr;
  257.             r->Count = Count;
  258.             Enque(&Runs, r);
  259.  
  260.             if (Verbose && !QuietSwt) printf("\tWriting\n");
  261.             for (i = 0; i < Count; i++) {
  262.                 fputs(SortArray[i], fint);
  263.                 if (errno) {
  264.                     perror("I/O error on intermediate file");
  265.                     exit(10);
  266.                     }
  267.                 }
  268.             if (Verbose && !QuietSwt) printf("    Run # %d\n", Runs.Count + 1);
  269.             Count = FillSortArray();
  270.             TotalRecs += Count;
  271.             }
  272.         if (!QuietSwt)
  273.             fprintf(stderr, "Total records read = %ld\n", TotalRecs);
  274.         if (fin != stdin) {
  275.             fclose(fin);
  276.             if ((fout = fopen(OutName, "w")) == NULL) {
  277.                 fprintf(stderr, "I can't create output file: %s", OutName);
  278.                 perror("");
  279.                 exit(7);
  280.                 }
  281.             }
  282.         errno = 0;
  283.         if (Verbose && !QuietSwt) printf("\tSorting\n");
  284.         qsort(SortArray, Count, sizeof(char far *), comp);
  285.         for (i = 0; i < Count; i++) {
  286.             fputs(SortArray[i], fout);
  287.             if (errno) {
  288.                 perror("I/O error on output file");
  289.                 exit(8);
  290.                 }
  291.             }
  292.         Merge();
  293.         }
  294.     unlink(IntName);
  295.     if (!QuietSwt)
  296.         fprintf(stderr, "Total records written = %ld\n", OutCount);
  297.     exit(0);
  298.     }
  299.  
  300.  
  301.  void
  302. GetArgs (int argc, char *argv[]) {
  303.     extern int      QuietSwt;
  304.     extern int        Verbose;
  305.  
  306.     int             i;
  307.     char           *p1, *p2;
  308.     struct KeyEntry *t;
  309.  
  310.     for (i = 1; i < argc; ++i) {
  311.         if (argv[i][0] != '-') continue;
  312.         if (!strcmp(argv[i], "-")) {
  313.             fin = stdin;
  314.             fout = stdout;
  315.             continue;
  316.             }
  317.         switch (tolower(argv[i][1])) {
  318.             case 't':
  319.                 strcpy(IntPath, &argv[i][2]);
  320.                 break;
  321.             case 'q':
  322.                 QuietSwt = 1;
  323.                 break;
  324.             case 'v':
  325.                 Verbose = 1;
  326.                 break;
  327.             default:
  328.                 fprintf(stderr, "Invalid option: %s\n", argv[i]);
  329.                 Usage();
  330.             }
  331.         }
  332.  
  333.     for (i = 1; i < argc; ++i) {
  334.         if (argv[i][0] == '-') continue;
  335.         if (fin == NULL) {
  336.             if (InputName[0] == '\0') {
  337.                 strcpy(InputName, argv[i]);
  338.                 continue;
  339.                 }
  340.             else if (OutName[0] == '\0') {
  341.                 strcpy(OutName, argv[i]);
  342.                 continue;
  343.                 }
  344.             }
  345.         p1 = argv[i];
  346.         if (!isdigit(p1[0])) InvalArgu(argv[i]);
  347.         if ((RecLen == -1) && (strspn(p1, "0123456789") == strlen(p1))) {
  348.             RecLen = atoi(argv[i]);
  349.             continue;
  350.             }
  351.         p2 = &p1[strspn(p1, "0123456789")];
  352.         if ((t = malloc(sizeof(struct KeyEntry))) == NULL) {
  353.             fprintf(stderr, "Insufficient memory for Key entry.\n");
  354.             exit(12);
  355.             }
  356.         t->Order = 'a';
  357.         t->Case = 'm';
  358.         t->Type = 'c';
  359.         t->Begin = atoi(p1) - 1;
  360.         if (*p2 == ':') t->Len = atoi(++p2);
  361.         else if (*p2 == '-') t->Len = atoi(++p2) - t->Begin;
  362.         else InvalArgu(argv[i]);
  363.         p1 = p2;
  364.         p2 = &p1[strspn(p1, "0123456789")];
  365.         if (*p2 == ':') {
  366.             p1 = ++p2;
  367.             while (*p1 != '\0') {
  368.                 switch (tolower(*p1++)) {
  369.                     case 'd':
  370.                         t->Order = 'd';
  371.                         break;
  372.                     case 'a':
  373.                         t->Order = 'a';
  374.                         break;
  375.                     case 'i':
  376.                         t->Case = 'i';
  377.                         break;
  378.                     case 'm':
  379.                         t->Case = 'm';
  380.                         break;
  381.                     case 'c':
  382.                         t->Type = 'c';
  383.                         break;
  384.                     default:
  385.                         InvalArgu(argv[i]);
  386.                     }
  387.                 }
  388.             }
  389.         else if (*p2 != '\0') InvalArgu(argv[i]);
  390.         Enque(Keys, t);
  391.         }
  392.     }
  393.  
  394.  void
  395. InvalArgu (char *Msg) {
  396.     fprintf(stderr, "Invalid argument: %s.\n", Msg);
  397.     Usage();
  398.     }
  399.  
  400.  
  401.  unsigned
  402. FillSortArray (void) {
  403.     int             i;
  404.  
  405.     if (Verbose && !QuietSwt) printf("\tReading\n");
  406.     for (i = 0; i < S_ArraySize; i++) {
  407.         if (fgets(Buffer, RecLen + 1, fin) == NULL) return (i);
  408.         if (errno) {
  409.             perror("I/O error on input file");
  410.             exit(3);
  411.             }
  412.         NextAdr = ftell(fin);
  413.         lnno++;
  414.         if ((strlen(Buffer) == RecLen) && (Buffer[strlen(Buffer) - 1] != '\n')) {
  415.             fprintf(stderr, "Record #%d exceeds maximum length %d\n",
  416.                     lnno, RecLen);
  417.             exit(4);
  418.             }
  419.         strcpy(SortArray[i], Buffer);
  420.         }
  421.     return (i);
  422.     }
  423.  
  424.  
  425.  int
  426. comp (const void *aa, const void *bb) {
  427.     char          **a, **b;
  428.     char            HoldA, HoldB;
  429.     int             End, Result;
  430.     QUE_ENTRY      *t;
  431.     struct KeyEntry *v;
  432.  
  433.     a = (char **) aa;
  434.     b = (char **) bb;
  435.     if (*a == *b) return (0);
  436.     if (*a == NULL) return (1);
  437.     if (*b == NULL) return (-1);
  438.     for (Result = 0, t = Keys->Head; (t != NULL) && (Result == 0); t = t->Next) {
  439.         v = t->Body;
  440.         End = v->Begin + v->Len;
  441.         HoldA = (*a)[End];
  442.         (*a)[End] = '\0';
  443.         HoldB = (*b)[End];
  444.         (*b)[End] = '\0';
  445.         Result = (v->Order == 'a') ?
  446.             (v->Case == 'i') ? stricmp(&(*a)[v->Begin], &(*b)[v->Begin])
  447.             : strcmp(&(*a)[v->Begin], &(*b)[v->Begin])
  448.             : (v->Case == 'i') ? stricmp(&(*b)[v->Begin], &(*a)[v->Begin])
  449.             : strcmp(&(*b)[v->Begin], &(*a)[v->Begin]);
  450.         (*a)[End] = HoldA;
  451.         (*b)[End] = HoldB;
  452.         }
  453.     return (Result);
  454.     }
  455.  
  456.  
  457.  void
  458. Usage (void) {
  459.     fprintf(stderr, "USAGE: pdsort input_file output_file rec_len\n");
  460.     exit(1);
  461.     }